2. СИНТАКСИС И СЕМАНТИКА ПРОЛОГ – ПРОГРАММЫ


CОДЕРЖАНИЕ

2.1. Переменные
2.2. Структуры
2.3. Сопоставление
2.4. Вопросы
2.5. Факты и правила
2.6. Алгоритм выполнения программы
2.7. Декларативный смысл пролог - программ
2.8. Структура Пролог - программы

 

СОДЕРЖАНИЕ

 

 

2.1. Переменные

 

Переменные в Прологе начинаются с заглавной буквы, применяются цифры и буквы латинского  алфавита. Особый вид переменной – анонимная переменная, используемая в качестве аргумента предиката, когда конкретное значение переменной не существует. Переменная в Прологе не является хранилищем информации, она существует, пока существует предложение. В процессе выполнения  программы переменная может развязываться и принимать новые значения. Примеры переменных:

 

Х

Результат

Объект2

Список_участников

СписокПокупок

_х23

_23

имеет_ребенка(Х):-родитель(Х,У).

 

Здесь свойство имеет_ребенка не зависит от имени ребенка, поэтому уместно применить анонимную переменную:

 

имеет_ребенка(Х):-родитель(Х,_).

некто_имеет_ребенка:-родитель(_,_).

 

Лексический диапазон имени - одно предложение. Это значит, что если, например, имя Х встречается в двух разных предложениях, то оно обозначает две разные переменные. Однако внутри одного предложения каждое его появление обозначает одну и ту же переменную. Для констант ситуация другая: один и тот же атом обозначает один и тот же объект в любом предложении, иначе говоря - во всей программе.

 

СОДЕРЖАНИЕ

2.2. Структуры

 

Структура-это конструкция, состоящая из имени структуры и заключенного в скобки списка ее аргументов, разделенных запятыми. Элементами структуры могут быть атомы, числа, списки. Для того, чтобы объединить компоненты в структуру, требуется выбрать функтур. Пример:

 

дата(1,май,1983) 

 

Здесь функтур – дата. Все компоненты в данном примере являются константами (две компоненты – целые числа и одна – атом). Произвольный день в мае можно представить структурой на рисунке 1:

дата(День,май,1983). 


 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 


Объекты, приведенные на рисунке 2 можно представить  следующими  прологовскими  термами:

 

Р1=точка(2,4).

Р2=точка(5,2).

S=отрезок(Р1,Р2)=отрезок(точка(2,4),точка(5,2)).

Т=треугольник(точка(2,4),точка(5,2),точка(7,6)).

 

 

СОДЕРЖАНИЕ

 

2.3. Сопоставление

 

Основная операция, выполняемая на языке Пролог – это операция сопоставления (называется также унификацией или согласованием). Эта операция может быть либо успешной, либо неуспешной. Переменные получают свои значения в результате сопоставления с константами в фактах и в правилах. До тех пор, пока переменная не получила своего значения,  она называется свободной. Когда переменная получит свое новое значение, она становится связанной. Однако она остается связанной только в течении времени, необходимого для получения ответа на запрос. После этого Пролог развязывает ее, возвращается и ищет альтернативные решения. Переменные служат частью процесса сопоставления. Операция сопоставления определяется так:

1. Константа сопоставляется только с константой.

2. Идентичные структуры сопоставляются друг с другом.

3. Переменная сопоставляется с  константой или с ранее известной переменной.

4. Две свободные переменные могут связываться и сопоставляться друг с другом. Примеры сопоставления:

 

число 5 сопоставляется с 5.

факт «имеет» сопоставляется с «имеет».

константа Сергей не  сопоставляется с константой Юрий.

 

 

СОДЕРЖАНИЕ

 

2.4. Вопросы

 

Вопрос-это отправная точка логического вывода, происходящего при выполнении программы. На любой вопрос система отвечает Да или Нет.


Напишем фрагмент программы для распознавания горизонтальных и вертикальных отрезков. Отрезок является вертикальным, если координаты его точек-концов совпадают; никаких других ограничений на отрезок не накладывается. Свойство «горизонтальности» формулируется аналогично, нужно только Х и У поменять местами. Следующая программа, содержащая эти факты, реализует эти формулировки:

 


верт(отр(точка(Х,У),точка(Х,У1))).

гор(отр(точка(Х,У),точка(Х1,У))).

 

С этой программой возможен такой диалог:

 

?-верт(отр(точка(4,2),точка(4,6))).

да

?-верт(отр(точка(1,1),точка(2,У))).

нет

?-гор(отр(точка(1,1),точка(7,У))).

У=1

 

Сформулируем более общий вопрос к программе: «Существуют ли какие-либо вертикальные отрезки, начало которых лежит в точке (2,3)?»

 

?-верт(отр(точка(4,2),Р)).

Р=точка(4,У)

 

Зададим следующий вопрос: Существует ли отрезок, который одновременно горизонтален и вертикален?

 

?-верт(S),гор(S).

S=отр(точка(Х,У),точка(Х,У)).

 

 

СОДЕРЖАНИЕ

 

2.5. Факты и правила

 

          Факты- это  предикаты с аргументами, константами, обозначающими отношения между объектами или свойства объектов. Факты всегда являются истинными и служат основой доказательства, происходящего при выполнении программы. Примеры  фактов:

 

Иванов(телефон, т123456).

Петров(телефон, т789012).

 

Правила  позволяют определить  новые отношения между объектами на основе уже имеющихся фактов. В качестве аргументов могут быть использованы константы, переменные. Структура правила:

 

<голова правила>:-<подцель1>,< подцель2>,..< подцельN>.

 

Где “:-“  - читается ЕСЛИ; “,” – означает И. В конце фактов и правил ставится точка. Пример правила:

 

Крутой_парень(Х):-любит(Х, рэп), носит(Х, блейзер).

 

Понимается так: Некто Х-крутой парень, если Х любит рэп и носит блейзер.

 

 

СОДЕРЖАНИЕ

 

2.6. Алгоритм выполнения программы

 

          Факты и правила программы  на Прологе являются описанием отношений и связей между объектами некоторой предметной области. Факт можно рассматривать как полностью определенную процедуру, для выполнения которой больше ничего ненужно. Правило:

 

А:-В1, В2,…, Вn

 

можно рассматривать как определение процедуры А, утверждающее, что для ее определения нужно знать В1, В2,…, Вn. Процедуры В1, В2,…, Вn выполняются в определенном порядке слева - направо. Если очередная процедура выполняется успешно, то осуществляется переход в следующую процедуру, если неуспешно, то переход к следующему варианту описания этой процедуры, которая определяется сверху - вниз. Поиск для согласования фактов и правил в базе знаний происходит последовательно сверху - вниз и если подходящих фактов не найдено, то ответ отрицательный. Пример:

 

Любит(оля, чтение).

Любит(света, бадминтон).

Любит(лена, плавание).

Любит(лена, чтение).

?-Любит(Х, чтение), любит(Х, плавание).

 

Вопрос означает, есть ли люди, которым нравится чтение и плавание. Сначала Пролог ищет факт сопоставления с первой частью запроса Любит(Х, чтение). Переменная Х связывается со значением оля, в то же время Пролог фиксирует в списке фактов указатель, показывающий состояние процедуры поиска. Далее Пролог пытается согласовать вторую часть запроса при Х=оля. Ищет факт Любит(оля, плавание). Такого факта нет и поиск завершается неуспешно. Тогда Пролог возвращается к первой части запроса Любит(Х, чтение), развязывает переменную Х и продолжает поиск, начиная с раннее установленного в списке фактов указателя. Подходит факт Любит(лена, чтение). Переменная Х сопоставляется значению лена и далее вторая часть запроса успешно согласуется с фактом Любит(лена, плавание). Выполнен поиск с возвратом.

 

 

СОДЕРЖАНИЕ

 

2.7. Декларативный смысл пролог - программ

 

Рассмотрим предложение:

 

Р:-Q,R.

 

Декларативная интерпретация:

 

1) Р- истинно, если Q,R истинны.

2) Из Q и R следует P

 

Процедурная интерпретация:

 

1)Чтобы решить задачу Р, сначала реши подзадачу Q, а затем – подзадачу R.

2)Чтобы достичь Р, сначала достигни Q, а затем R.

 

Запятая между целями обозначает конъюнкцию целей: они все должны быть истинными. Однако в прологе возможна и дизъюнкция целей: должна быть истинной по крайней мере одна из целей. Дизъюнкция обозначается точкой с запятой. Например:

 

1) Р:-Q;R. или:

2) Р:-Q.

    Р:-R.

1)<=>2)

 

Запятая связывает (цели) сильнее, чем точка с запятой. Таким образом, предложение:

 

Р:-Q,R;S,T,U.

 

понимается как: 1)Р:-(Q,R);(S,T,U). или: 2) Р:-Q,R.

                                                                       P:-S,T,U.

 

 

СОДЕРЖАНИЕ

 

2.8. Структура Пролог - программы

 

Структура программы имеет следующий вид:

/* комментарии на нескольких строках */

% комментарии на одной строке

CONSTANTS

 %В этом разделе описываются константы

DOMAINS

%В этом разделе описываются переменные

PREDICATES

%В этом разделе определяются предикаты

CLAUSES

%В этом разделе определяются факты и правила

DATABASES

%В этом разделе определяются предикаты динамической базы данных

GOAL

%В этом разделе определяются запросы (внутренние)

 

Домены подразделяются на простые, структурированные и нестандартные. К стандартным доменам относятся: symbol, char, integer, real, string, file.

symbol - символьный тип данных,  имеет  две формы записи: 1.  последовательность  букв и цифр,  знаков подчеркивания, начинающаяся со строчной (маленькой буквы); 2. последовательность символов, заключенная в двойные кавычки.

char-один символ.

integer – целое число  в диапазоне: -32768…32768

real- действительное  число, допускается обычная и экспоненциальная  форма записи.

string-строка символов, любая последовательность символов, заключенная в двойные кавычки.

file-файловая  переменная, значение ее определяется по правилам именования файлов в MS DOS. Примеры объявления  доменов:

 

DOMAINS

  a=integer

  b=symbol

 

Кроме стандартных типов доменов можно  использовать структуры доменов, состоящих из простых и сложных объектов. В одном объявлении можно описывать несколько структур,  разделяя их точкой с  запятой, или служебным словом or:

 

DOMAINS

 d1,d2,d3=symbol

 f=fruits(d1,d2,d3); p(d3)

 

В разделе предикатов описывается левая часть правила или заголовок  правила из раздела CLAUSES.

В разделе CLAUSES описываются утверждения. Правила и факты, имеющие один точный предикат должны  записываться в рамках одного блока, то есть следовать  один за  другим. В теле правила кроме объявленных предикатов могут использоваться стандартные  предикаты и операции сравнения. Стандартные предикаты выполняют разнообразные функции по вводу и выводу, работе с файлами, с операционной системой DOS, обработке строк, поддержке графического режима, обеспечения интерфейса с другими системами программирования.

Раздел GOAL содержит запрос к программе, называемый внутренним. Для внутреннего запроса Пролог осуществляет поиск первого подходящего решения, при этом система не сообщает о результатах найденного решения, полученные при сопоставлении. Эти действия должны быть запрограммированы. Раздел запросов GOAL может отсутствовать в программе, тогда в диалоговом режиме после запуска  программы можно внести внешний запрос. Для использования внешнего запроса система отыскивает все варианты  решений, и в этом же окне выводятся значения переменных предикатов и сообщение об успешном или неуспешном выполнении.